Everything about Diagonal Lemma totally explained
In
mathematical logic, the
diagonal lemma or
fixed point theorem establishes the existence of
self-referential sentences in formal theories of the
natural numbers, if those theories are strong enough to represent all
computable functions. Such sentences can be used to prove fundamental results such as
Gödel's incompleteness theorems and
Tarski's indefinability theorem.
Background
Let
N be the set of
natural numbers. A
theory T represents the function
f :
N→
N if there exists a formula δ(
x,
y) in the language of
T such that for each
n,
T proves
» ∀
y [
f(
n)=
y ↔ δ(
n,
y)].
Here
n is the numeral corresponding to the natural number
n; it's defined to be the closed term 1+ ··· +1 (
n ones).
The diagonal lemma applies to theories capable of representing the functions that make up
primitive recursive arithmetic. Such theories include
Peano arithmetic and the weaker
Robinson arithmetic.
The diagonal lemma also requires that there be a systematic way of assigning to every formula θ a natural number #(θ) called its
Gödel number. Formulas can then be represented within the theory by the numerals corresponding to their Gödel numbers.
Statement of the lemma
Let
T be a
first-order theory in the language of arithmetic and capable of representing all
computable functions. Let ψ be a formula in the theory
T with one free variable. The diagonal lemma states that there's a sentence φ in
T such that φ ↔ ψ(
#(φ)) is provable in
T.
Intuitively, φ is a
self-referential sentence saying that φ has the property ψ. The sentence φ can also be viewed as a
fixed point of the operation assigning to each formula θ the sentence ψ(
#(θ)). The sentence φ constructed in the proof isn't literally the same as ψ(
#(φ)), but is provably equivalent to it in the theory
T.
Proof
Let
f:
N→
N be a function such that:
» f(#(θ)) = #(θ(
#(θ))
for any any formula θ in the theory
T having one free variable. If
n isn't the Gödel number of a formula, then
f(
n) = 0. The function
f is computable, so there's a formula
δ representing
f in
T. Thus for each formula θ,
T proves
» ∀
y [
y =
#(θ(#(θ)) ↔ δ(
#(θ),y)].
Now define the formula β(x) as:
» β(x) = ∀
y [δ(
x,
y)→ ψ(
y)].
Let φ be the sentence β(
#(β)). Then we can prove in
T that:
» (*) φ ↔ ∀
y [ δ(
#(β),
y) → ψ(
y)] ↔ ∀
y [ (
y =
#(β(#(β))) → ψ(
y)].
We analyze two cases.
1. Assuming φ holds, substitute #(β(
#(β)) for
y in the rightmost formula in (*), and obtain:
» (
#(β(#(β)) =
#(β(#(β))) → ψ(
#(β(#(β))),
Since φ = β(
#(β)), it follows that ψ(
#(φ)) holds.
2. Conversely, assume that ψ(
#(β(#(β))) holds. Then the final formula in (*) must be true, and φ is also true.
Thus φ ↔ ψ(
#(φ)) is provable in
T, as desired.
History
The diagonal lemma is closely related to
Kleene's recursion theorem in
computability theory, and their respective proofs are quite similar.
The lemma is called "diagonal" because it bears some resemblance to
Cantor's diagonal argument. The terms "diagonal lemma" or "fixed point" don't appear in
Kurt Gödel's epochal 1931 article, or in Tarski (1936). Carnap (1934) was the first to prove that for any formula ψ in a theory
T satisfying certain conditions, there exists a formula φ such that φ ↔ ψ(
#(φ)) is provable in
T. Carnap's work was phrased in alternate language, as the concept of
computable functions wasn't yet developed in 1934. Mendelson (1997, p. 204) believes that Carnap was the first to state that something like the diagonal lemma was implicit in Gödel's reasoning. Gödel was aware of Carnap's work by 1937.
Further Information
Get more info on 'Diagonal Lemma'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://diagonal_lemma.totallyexplained.com">Diagonal lemma Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
